package it.unibz.easytravel.expenses.statistic;

import it.unibz.easytravel.common.Person;
import it.unibz.easytravel.expenses.Debt;

import java.util.Vector;

import android.util.Log;

public class Statistic {
	private boolean calculated = false;
	private Vector<Debt> debts;
	private Vector<Debt> newEnties;
	private Vector<Person> travelers;
	
	public Statistic(Vector<Debt> debts){
		this.debts = debts;
		logDebts(debts);
	}
	
	public Vector<Debt> getDebts() {
		if (!calculated){
			newEnties = new Vector<Debt>();
            // set used & executed flag to false
			int debts_size = debts.size();
			for (int i = 0; i < debts_size; i++) {
				((Debt)debts.elementAt(i)).setUsed(false);
				((Debt)debts.elementAt(i)).setExecuted(false);
			}
			
			
			
			// put root nodes in the front
			Vector<Debt> rootUp = new Vector<Debt>();
			Debt t,t2;
			//puts the connections with the root to the top of the vector 
			for (int i = 0; i < debts_size; i++) {
				t = (Debt)debts.elementAt(i);
				if(!t.isUsed()){
					boolean found = false;
					
					for (int j = 0; j < debts_size; j++) {
					    t2 = (Debt)debts.elementAt(j);
						if(t.getCreditor().equals(t2.getCreditor()))
							((Debt)debts.elementAt(j)).setUsed(true);
						if(t.getCreditor().equals(t2.getDebtor()))
							found = true;
					}
					if(!found){
						for (int j = 0; j < debts_size; j++) {
							t2 = (Debt)debts.elementAt(j);
							if(t.getCreditor().equals(t2.getCreditor())){
								rootUp.addElement(t2);
								((Debt)debts.elementAt(j)).setExecuted(true);
							}
						}	
					}
				}
			}
			
			//add not roots to "rootUp" vector
			for (int i = 0; i < debts_size; i++) {
				if(!((Debt)debts.elementAt(i)).isExecuted())
					rootUp.addElement(debts.elementAt(i));
			}

			Vector<Debt> opt = new Vector<Debt>();
			for (int i = 0; i < debts.size(); i++) {
				t = (Debt)debts.elementAt(i);
				t.setUsed(false);
				t.setExecuted(false);
				opt.addElement(t);
			}
			
			for (int i = 0; i < opt.size(); i++) {
				if(!((Debt)opt.elementAt(i)).isExecuted()){
					createRelationGraph(opt, i, 1);
					rearangeLevels(opt);
					opt = shift(opt);
				}
			}			
			
			//add results and merge if necessary
			for (int j = 0; j < debts.size(); j++) {
				Debt tmp = (Debt)debts.elementAt(j);
				for (int i = 0; i < newEnties.size(); i++) {
					Debt tmp2 = (Debt)newEnties.elementAt(i);
					if(tmp.getCreditor().equals(tmp2.getCreditor()) &&
							tmp.getDebtor().equals(tmp2.getDebtor()) && 
							!tmp2.isUsed()){
						tmp.setDebt(tmp.getDebt()+tmp2.getDebt());
						tmp2.setUsed(true);
					}
				}
			}
			for (int i = 0; i < newEnties.size(); i++) {
				if(!((Debt)newEnties.elementAt(i)).isUsed()){
					debts.addElement(newEnties.elementAt(i));
				}
			}

			//filter 0's
			Vector<Debt> result = new Vector<Debt>();
			for (int i = 0; i < debts.size(); i++)
				if(((Debt)debts.elementAt(i)).getDebt() != 0)
					result.addElement(debts.elementAt(i));

			//merge same elements

			this.debts = removeEqual(result);
			calculated = true;
			return this.debts;
		}
		
		return debts;
	}

	
	/**
	 * 
	 * @param debts
	 * @return the list of debtors where debtor and payer overlaps are covered.
	 */
	private Vector removeEqual(Vector debts){
		newEnties = new Vector(); 
		for (int i = 0; i < debts.size(); i++) {
			Debt t = (Debt)debts.elementAt(i);
			if(t.getDebt() == 0){continue;}
			for (int j = i+1; j < debts.size(); j++) {
				Debt s = (Debt)debts.elementAt(j);
				if(t.getDebtor().equals(s.getDebtor()) &&
				   t.getCreditor().equals(s.getCreditor()))
				
				{	
					t.setDebt(t.getDebt()+s.getDebt());
					s.setDebt(0);
				}
			}
			newEnties.addElement(t);
		}
		return newEnties;
	}
	
	private Vector<Debt> shift(Vector<Debt> v){
		// copy result set
		Vector<Debt> set = new Vector<Debt>();
		Vector<Debt> remainings = new Vector<Debt>();
		for (int i = 0; i < v.size(); i++) {
			Debt debt = (Debt)v.elementAt(i);
			if(debt.isUsed() && !debt.isExecuted()){
				set.addElement(debt);
			}else{
				remainings.addElement(debt);
			}
		}
		//get everything in desc order (buble sort)
		for (int i = 0; i < set.size(); i++) {
			for (int j = set.size()-1; j >= i+1; j--) {
				if(((Debt)set.elementAt(j)).getLevel() > ((Debt)set.elementAt(j-1)).getLevel()){
					Debt tmp = (Debt)set.elementAt(j);
					set.setElementAt(set.elementAt(j-1), j);
					set.setElementAt(tmp, j-1);
				}
			}
		}
		for (int i = 0; i < set.size(); i++) {
			((Debt)set.elementAt(i)).setIndex(i);
		}

		//shift
		makeShift(set);	

		//apply changes from set to v
		for (int j = 0; j < set.size(); j++) {
			Debt toChange = (Debt)set.elementAt(j);
			//			toChange.setExecuted(true);
			v.setElementAt(toChange, toChange.getIndex());		
		}

		// put remainings back to Vector
		for (int i = 0; i < remainings.size(); i++) {
			set.addElement(remainings.elementAt(i));
		}

		//print		
		//		System.out.println("print");
		//		for (int i = 0; i < set.size(); i++) {
		//			Debt setd = (Debt)set.elementAt(i);
		//			System.out.println(setd.getPayer()+" <- "+setd.getDebtor()+"\t"+setd.getDebt()+"\t"+setd.getLevel());
		//		}

		return set;
	}
	
	private void makeShift(Vector set) {
		for (int l = 0; l < set.size(); l++) {

			//			System.out.println("\nprint");
			//			for (int i = 0; i < set.size(); i++) {
			//				Debt setd = (Debt)set.elementAt(i);
			//				System.out.println(setd.getPayer()+" <- "+setd.getDebtor()+"\t"+setd.getDebt()+"\t"+setd.getLevel());
			//			}
			//			System.out.println("print new entries");
			//			for (int i = 0; i < newEnties.size(); i++) {
			//				Debt setd = (Debt)newEnties.elementAt(i);
			//				System.out.println(setd.getPayer()+" <- "+setd.getDebtor()+"\t"+setd.getDebt()+"\t"+setd.getLevel());
			//			}
			//			

			Vector path = new Vector();
			optPath(set,l,path);

			//print best path
			//			System.out.println("best path");
			//			for (int k = 0; k < path.size(); k++) {
			//				Debt setd = (Debt)path.elementAt(k);
			//				System.out.println(">> "+setd.getPayer()+" <- "+setd.getDebtor()+"\t"+setd.getDebt()+"\t"+setd.getLevel()+" i> "+setd.getIndex());
			//			}

			//find min value
			int min = 1000000000;
			for (int j = 0; j < path.size(); j++) {
				if(((Debt)path.elementAt(j)).getDebt() < min){
					min = ((Debt)path.elementAt(j)).getDebt();
				}
			}
			if(path.size()<=1) min = 0;

			//			System.out.println(min);

			//optimize by min value | current - min
			for (int j = 0; j < path.size(); j++) {
				Debt toChange = (Debt)path.elementAt(j);
				//toChange.setDebt(toChange.getDebt() - min);
				Debt tc = (Debt)set.elementAt(toChange.getIndex());
				tc.setDebt(toChange.getDebt() - min);
			}

			//			create new entry
			Debt newDebt = new Debt(((Debt)path.lastElement()).getCreditor(),
					((Debt)path.elementAt(0)).getDebtor(),
					min); 
			newEnties.addElement(newDebt);

		}				
	}
	
	private Vector optPath(Vector set, int i, Vector path){
		Debt d;

		d = (Debt)set.elementAt(i);
		path.addElement(d);


		// get optimal path
		int max = -1;
		int index = -1;
		for (int j = 0; j < set.size(); j++) {
			Debt d2 = (Debt)set.elementAt(j);
			if(d.getCreditor().equals(d2.getDebtor())){
				if(max < d2.getDebt()){
					max = d2.getDebt();
					index = j;
				}
			}
		}
		if(index == -1 ) return path;
		optPath(set,index,path);
		return path;
	}
	
	private void createRelationGraph(Vector v, int root, int level){

		Debt rootElem = (Debt)v.elementAt(root);
		if(!rootElem.isUsed()){ 
			rootElem.setLevel(level++);
			rootElem.setUsed(true);
			//			System.out.println(rootElem.getPayer()+"\t"+rootElem.getDebtor()+"\t"+rootElem.getDebt()+"\t"+rootElem.getLevel());

			for (int i = 0; i < v.size(); i++) {
				if(rootElem.getDebtor().equals(((Debt)v.elementAt(i)).getCreditor())){
					if(!((Debt)v.elementAt(i)).isUsed())createRelationGraph(v,i,level);
				}
			}
		}
	}

	private void rearangeLevels(Vector opt) {
		for (int i = 0; i < opt.size(); i++) {
			Debt debt = (Debt)opt.elementAt(i);
			if(debt.isUsed() && !debt.isExecuted()){
				// get max layer nr
				int max = debt.getLevel();
				for (int j = 0; j < opt.size(); j++) {
					Debt debt2 = (Debt)opt.elementAt(j);
					if(debt2.isUsed() && !debt2.isExecuted() && debt.getDebtor().equals(debt2.getDebtor())){
						if(max < debt2.getLevel()){
							max = debt2.getLevel();
						}
					}
				}
				//set max
				for (int j = 0; j < opt.size(); j++) {
					Debt debt3 = (Debt)opt.elementAt(j);
					if(debt.isUsed() && !debt.isExecuted() && debt3.getDebtor().equals(debt.getDebtor())){
						((Debt)opt.elementAt(j)).setLevel(max);
					}
				}
			}
		}

	}
		
	/**
	 * 
	 * @return The list of debts in the Vector<Debt>
	 */
	public void logDebts(Vector d){
		String str="";
		int size = d.size();
		for (int i = 0; i < size; i++) {
			str+=d.elementAt(i).toString();
		}
		Log.i("Debts_List", str);
	}
	
	/**
	 * 
	 * @return The list of debts in the Vector<Debt>
	 */
	public String printDebts(){
		String str="";
		int size = debts.size();
		for (int i = 0; i < size; i++) {
			str+=debts.elementAt(i).toString();
		}
		return str;
	}
	/**
	 * @param Vector<Debt> to print
	 * @return The list of debts in the Vector<Debt>
	 */
	public String printDebts(Vector<Debt> debts){
		String str="";
		int size = debts.size();
		for (int i = 0; i < size; i++) {
			str+=debts.elementAt(i).toString(true);
		}
		return str;
	}
	/**
	 * 
	 * @return The list of debts in the Vector<Debt>
	 */
	public String printTravelers(){
		String str="";
		int size = travelers.size();
		for (int i = 0; i < size; i++) {
			str+=travelers.elementAt(i).toString();
		}
		return str;
	}
}
